package basic.basic_class02;

public class Code_04_Manacher {

	/**
	 * 将待查找的数组添加虚轴改造为字符数组
	 * @param str
	 * @return
	 */
	public static char[] manacherString(String str) {
		// 首先将字符串转化为字符数组
		char[] charArr = str.toCharArray();
		// 将字符数组扩大两倍再加1，保证数组长度必为奇数
		char[] res = new char[str.length() * 2 + 1];
		// 将原始字符数组两两之间添加虚轴“#”
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			// 元素下标为偶数则添加“#” 为奇数则添加原始数组中的元素
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	/**
	 * Manacher函数主体：给定一个字符串，返回最大的回文子串的长度
	 * @param str
	 * @return
	 */
	public static int maxLcpsLength(String str) {
		// 首先如果字符串长度为0或者为null，返回0
		if (str == null || str.length() == 0) {
			return 0;
		}
		// 改造原始字符串，添加虚轴
		char[] charArr = manacherString(str);
		// 创建辅助数组，用于记录当前位置的回文半径
		int[] pArr = new int[charArr.length];
		// 初始化当前最大回文右边界的中心位置
		int index = -1;
		// 初始化最大回文右边界的位置为-1
		int pR = -1;
		int max = Integer.MIN_VALUE;
		// 遍历改造过后的数组
		for (int i = 0; i != charArr.length; i++) {
			// 首先如果当前的最大右边界大于i ， 也就是说i再LR边界里面，那么i位置的回文半径为（前面i·的回文与当前R与i距离的最小值）
			// 如果当前的i在最大右边界外面或者相等，则此处的回文半径置为1
			pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
				// 以i作为回文中心，暴力扩
				if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
					pArr[i]++;
				else {
					// 如果不相等了，则break掉，退出循环，
					break;
				}
			}
			// 扩展最大的回文右边界和相应的回文中心
			if (i + pArr[i] > pR) {
				pR = i + pArr[i];
				index = i;
			}
			// 每次填上一个值的时候，取当前回文半径中的最大值
			max = Math.max(max, pArr[i]);
		}
		// 因为字符数组是加了虚轴之后进行筛选的，所以返回整体的长度是，直接返回max-1即可
		return max - 1;
	}

	public static void main(String[] args) {
		String str1 = "abc1234321ab";
		System.out.println(maxLcpsLength(str1));
	}

}
